package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 103. 二叉树的锯齿形层序遍历
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[20,9],[15,7]]
 * 示例 2：
 * <p>
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 * <p>
 * 输入：root = []
 * 输出：[]
 */
public class ZigzagLevelOrder {

    /**
     * 这个写法不太优雅，可以把正反方向的逻辑放在res变量里实现
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        // 层序遍历，变种

        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        boolean order = false;

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {

            int size = queue.size();
            List<Integer> res = new ArrayList<>();

            while (size > 0) {
                size--;
                TreeNode treeNode;
                // 正序
                if (order) {
                    treeNode = queue.pollFirst();
                } else {
                    treeNode = queue.pollLast();
                }

                res.add(treeNode.val);

                if (order) {
                    if (treeNode.right != null)
                        queue.offerLast(treeNode.right);
                    if (treeNode.left != null)
                        queue.offerLast(treeNode.left);
                } else {
                    if (treeNode.left != null)
                        queue.offerFirst(treeNode.left);
                    if (treeNode.right != null)
                        queue.offerFirst(treeNode.right);
                }
                size--;
            }
            order = !order;
            ans.add(res);
        }
        return ans;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }
}
